package com.wc.算法提高课.C第三章_图论.单源最短路的扩展应用.拯救大兵瑞恩;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

/**
 * @Author congge
 * @Date 2024/10/12 16:26
 * @description https://www.acwing.com/problem/content/1133/
 */
public class Main {
    /**
     * 思路：bfs + 状态压缩
     */
    static FastReader sc = new FastReader();
    static PrintWriter out = new PrintWriter(System.out);
    static int N = 11, M = 4 * N * N, P = 1 << N, INF = 0x3f3f3f3f;
    // M代表墙的状态
    static int[] h = new int[M], e = new int[M], ne = new int[M], w = new int[M];
    static int[][] g = new int[N][M];
    // 检查四面是否使用
    static boolean[][][] vis = new boolean[N][N][4];
    // 上 左 右 下, 0 1 2 3
    static int[] dx = {-1, 0, 0, 1}, dy = {0, -1, 1, 0}, key = new int[M];
    static int[][] dist = new int[M][P];
    static boolean[][] st = new boolean[M][P];
    static int n, m, p, k, idx = 1;

    public static void main(String[] args) {
        n = sc.nextInt();
        m = sc.nextInt();
        p = sc.nextInt();
        k = sc.nextInt();
        for (int i = 1, t = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                g[i][j] = t++;
            }
        }
        while (k-- > 0) {
            int x1 = sc.nextInt(), y1 = sc.nextInt(), x2 = sc.nextInt(), y2 = sc.nextInt(), c = sc.nextInt();
            // 代表在哪一个面
            int pos = getPos(x1, y1, x2, y2);
            vis[x1][y1][pos] = true;
            vis[x2][y2][3 - pos] = true;
            if (c > 0) {
                int a = g[x1][y1], b = g[x2][y2];
                add(a, b, c);
                add(b, a, c);
            }
        }
        int s = sc.nextInt();
        while (s-- > 0) {
            int x = sc.nextInt(), y = sc.nextInt(), c = sc.nextInt();
            key[g[x][y]] += 1 << c - 1;
        }
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                for (int u = 0; u < 4; u++) {
                    if (!vis[i][j][u]) {
                        int x = i + dx[u], y = j + dy[u];
                        if (x <= 0 || x > n || y <= 0 || y > m) continue;
                        int a = g[i][j], b = g[x][y];
                        add(a, b, 0);
                    }
                }
            }
        }
        out.println(bfs());
        out.flush();
    }

    static int bfs() {
        for (int i = 1; i <= n * m; i++) {
            Arrays.fill(dist[i], INF);
        }
        dist[1][0] = 0;
        Queue<int[]> q = new LinkedList<>();
        // x y state
        q.add(new int[]{1, 0});
        while (!q.isEmpty()) {
            int[] node = q.poll();
            int t = node[0], state = node[1];
            if (t == n * m) return dist[t][state];
            if (st[t][state]) continue;
            st[t][state] = true;
            if (key[t] > 0) {
                if (dist[t][state | key[t]] > dist[t][state]) {
                    dist[t][state | key[t]] = dist[t][state];
                    q.add(new int[]{t, state | key[t]});
                }
            }
            for (int i = h[t]; i > 0; i = ne[i]) {
                int j = e[i];
                if (w[i] > 0 && (state >> w[i] - 1 & 1) != 1) continue;
                if (dist[j][state] > dist[t][state] + 1) {
                    dist[j][state] = dist[t][state] + 1;
                    q.add(new int[]{j, state});
                }
            }
        }
        return -1;
    }

    static int getPos(int x1, int y1, int x2, int y2) {
        for (int i = 0; i < 4; i++) {
            int a = x1 + dx[i], b = y1 + dy[i];
            if (a == x2 && b == y2) return i;
        }
        return -1;
    }

    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}

class FastReader {
    StringTokenizer st;
    BufferedReader br;

    FastReader() {
        br = new BufferedReader(new InputStreamReader(System.in));
    }

    String next() {
        while (st == null || !st.hasMoreElements()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    int nextInt() {
        return Integer.parseInt(next());
    }

    String nextLine() {
        String s = "";
        try {
            s = br.readLine();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return s;
    }

    long nextLong() {
        return Long.parseLong(next());
    }

    double nextDouble() {
        return Double.parseDouble(next());
    }

    // 是否由下一个
    boolean hasNext() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                String line = br.readLine();
                if (line == null)
                    return false;
                st = new StringTokenizer(line);
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }
        return true;
    }
}
